import java.util.*;

public class Main {
}

// 前k个高频单词
class Solution {
    public static void main(String[] args) {
        String[] words = {"i","love","leetcode","i","love","coding"};
        List<String> list = topKFrequent(words,3);
        System.out.println(list);

    }
    public static List<String> topKFrequent(String[] words, int k) {
        // 1、统计每个单词出现的次数
        Map<String, Integer> map = new HashMap();
        for(String s : words) {
            if(map.get(s) == null){
                map.put(s,1);
            }else{
                int val = map.get(s);
                map.put(s, val+1);
            }
        }

        // 注意：需要给minHeap传一个比较器，因为entry本身不可比较
        PriorityQueue<Map.Entry<String,Integer>> minHeap =
                new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        // entry和topHeap的value相等时，以key从小到大排序，是大堆的方式。
                        if (o1.getValue().compareTo(o2.getValue()) == 0){
                            return o2.getKey().compareTo(o1.getKey());
                        }
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });

        // 注意:题目要求先以次数(value)从大到小打印，次数相等的以字母(key)从小到大打印
        // 2、遍历Map，把key和value打包成entry，然后把前k个放入小堆priorityQueue中，
        //   之后的元素entry的value就和小堆中堆顶元素的value比较，比topHeap大，就让topHeap出堆，entry入堆
        //   如果value相等，那就用key比较，比topHeap的key小的entry入堆(相当于在value相等的元素使用大堆排序)
        Set<Map.Entry<String,Integer>> set = map.entrySet();
        for (Map.Entry<String,Integer> entry : set) {
            if(minHeap.size() < k){
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> topHeap = minHeap.peek();
                if (entry.getValue().compareTo(topHeap.getValue()) > 0){
                    minHeap.poll();
                    minHeap.offer(entry);
                } else if (entry.getValue().compareTo(topHeap.getValue()) == 0) {
                    if (entry.getKey().compareTo(topHeap.getKey()) < 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

        // 3、把minHeap中的entry出堆同时把的key逐个存入list
        List<String> list = new ArrayList<>();
        while(minHeap.size() > 0){
            String key = minHeap.poll().getKey();
            list.add(key);
        }

        // 4、因为此时key集合是从小堆中拿出的，在list中的顺序次数是从小到大
        // 调用Collections的reverse方法转置key集合，让key集合变成大到小
        Collections.reverse(list);
        return list;
    }
}